
import java.util.*;
/**
 * 
 * @author Matthew Dye 
 * @version 1 6/17/11
 *
 */
public class Sorter<T extends Comparable <T>> {
/**
 * selectionSort will sort a given method using the Selection Sort Algorithm. 
 * @param array
 * 			Array to be Sorted
 */
	public void selectionSort(T[] array)
	{
		int min = 0;
		int position = 0;
		for (position = 0; position < array.length; position++)
		{
			min = position;	
			for(int i = position +1; i<array.length; i++)
			{
				if(array[i].compareTo(array[min]) < 0)
					{
						min = i;
					}
			}	
			if( min != position)
			{
				swap(array,position,min);
			}		
		}
	}
/**
 * A method to swap two elements in an array to be sorted
 * @param array
 * 		Array to be sorted
 * @param firstIndex
 * 		First element to be swapped
 * @param secondIndex
 * 		Second element to be swapped
 */
	private void swap(T[] array, int firstIndex, int secondIndex)
	{
		T temp = array[firstIndex];
		array[firstIndex] = array[secondIndex];
		array[secondIndex] = temp;
		selectionSort(array);
	}
/**
 * Insertion Sort public method that calls the private method
 * @param array
 * 		Arary to be sorted
 */
	public void insertionSort(T[] array)
	{
		insertionSort(array, 0, array.length);
	}
/**
 * Insertion Sort method to sort an array following the insertion sort algorithm
 * @param array
 * 		Array to be sorted
 * @param first
 * 		Sub array first index
 * @param last
 * 		Sub array last index
 */
	private void insertionSort(T[] array, int first, int last)
	{
		for (int i = first; i < last; i++)
		{
			  int current = i;
			  T firstUnsorted = array[i];
			  
			  while ((current > 0) && (array[current-1].compareTo(firstUnsorted) >0))
			  {
				  array[current] = array[current-1];
				  current--;
			  }
			  	array[current] = firstUnsorted;
		}
	}
	
/**
 * Merge sort that calls the private method	
 * @param array
 * 		Array to be sorted
 */
	public void mergeSort( T[] array ) 
	{
        mergeSort( array, 0, array.length-1 );
    }
    
/**
 * Merge Sort method that recursively splits an array down will size 3 and calls the merge method on each one
 * @param array
 * 		Array to be sorted
 * @param left
 * 		Left bound of the sub array to be merged
 * @param right
 * 		Right bound of the sub array to be sorted
 */
    private void mergeSort(T[] array, int left, int right ) {
    	if(array.length < 3 )
    		insertionSort(array);
    	else
    	{
    		if(right == array.length)
    			right = right -1;
	    	if( left < right ) 
	        {
	            int center = ( left + right ) / 2;
	            mergeSort( array, left, center );
	            mergeSort( array, center + 1, right );
	            merge( array, left, center + 1, right );
	        }
    	}
    }
    
/**
 * Merge method that combines two sub arrays by sorting them in to each other
 * @param array
 * 		Array to be sorted
 * @param left
 * 		Left bound of the first sub array
 * @param mid
 * 		Right bound of the first sub array and left bound of second sub array
 * @param last
 * 		Right bound of second sub array
 */
    private void merge( T[ ] array, int left, int mid, int last ) 
    {
    	
		@SuppressWarnings("unchecked")
		T[] tmpArray = (T[])new Comparable[array.length];
        int leftEnd = mid - 1;
        int tmpPos = left;
        int numElements = last - left + 1;
        
        // Main loop
        while( left <= leftEnd && mid <= last )
            {
	        	if(array[left].compareTo(array[mid]) <= 0)
	                tmpArray[tmpPos++] = array[left++];
	            else
	                tmpArray[tmpPos++] = array[mid++];
            }
        
        while( left <= leftEnd )    // Copy rest of first half
            tmpArray[ tmpPos++ ] = array[ left++ ];
        
        while( mid <= last )  // Copy rest of right half
            tmpArray[ tmpPos++ ] = array[ mid++ ];
        
        // Copy tmpArray back
        for( int i = 0; i < numElements; i++, last--)
            array[last] = tmpArray[last];
    }
/**
 * Quick sort method that makes a call to the private quick sort method
 * @param array
 * 		Array to be sorted
 */
	public void quickSort(T[] array)
	{
		quickSort(array,0,array.length);
	}
/**
 * Quick sort method that will recurisvely call quick sort on subarrays	
 * @param array
 * 		Array to be sorted
 * @param first
 * 		First index of the sub array to be sorted
 * @param last
 * 		Right bound of the sub array to be sorted
 */
	public void quickSort(T[] array, int first, int last)
	{
		if(array.length < 3)
			insertionSort(array,0,3);
		else if(last-first+1 <3)
			insertionSort(array,first,last);
		else
		{
			int pivotIndex = partition(array,first,last-1);
			
			quickSort(array,first,pivotIndex-1);
			quickSort(array,pivotIndex+1,last);
		}
	}
/**
 * Partition method that chooses a random pivot to sort other elements in comparison to while also placing elements in their proper
 * place based upon the pivot	
 * @param array
 * 		Array to be sorted
 * @param first
 * 		Left bound of subarray to be sorted
 * @param last
 * 		Right bounf of sub array to be sorted
 * @return
 * 		Location of pivot element
 */
	public int partition(T[] array, int first, int last)
	{
		Random rand = new Random();
		int pivotIndex = rand.nextInt(last-first) + first;
		T pivot = array[pivotIndex];
		int left = first;
		int right = last - 1;
		
		boolean done = false;
		while(!done)
		{
			while(array[left].compareTo(pivot) < 0 && left <= last)
				left++;
			while(array[right].compareTo(pivot)>0 && right >= first)
				right--;
			assert array[left].compareTo(pivot) >= 0 && array[right].compareTo(pivot) <=0;
			if(left<right)
			{
				swap(array,left,right);
				left++;
				right++;
			}
			else 
				done = true;
		}
		swap(array,pivotIndex,left);
		pivotIndex = left;
		return pivotIndex;
	}

}
